//
// Description: 137. 只出现一次的数字 II
// Created by Loading on 2025/4/4.
//

#include <bits/stdc++.h>

using namespace std;

int singleNumber(vector<int> &nums) {
    /// 相当于每个元素的二进制每一位数字1的个数相加mod3
    // 位运算自动机，状态0为有3的倍数个1（3个一循环）
    // 状态0时，x为1，则状态1为1，状态2为0，转换为状态1
    // 状态1时，x为1，则状态1为0，状态2为1，转换为状态2
    // 状态2时，x为1，则状态1为0，状态2为0，转换为状态0
    // 状态1时，x为0，则状态1为1，状态2为0，仍为状态1
    // 状态2时，x为0，则状态1为0，状态2为1，仍为状态2
    int a = 0; // 状态1，有1个1
    int b = 0; // 状态2，有2个1
    for (auto &x : nums) {
        int tmp = a;
        a = a ^ x & ~b; // 转换为状态1的方式：a与x不同且b为0
        b = b ^ x & (b ^ tmp); // 转换为状态2的方式：b与x不同且a与b不同
    }

    // 返回状态1
    return a;
}

int main() {
    vector<int> nums{0, 1, 0, 1, 0, 1, 99, 2, 2, 2, 3, 3, 3, 4, 4, 4};

    auto res = singleNumber(nums);

    cout << res << endl;

    return 0;
}
